package leetcode;

//给定一个非负整数数组，你最初位于数组的第一个位置。
//数组中的每个元素代表你在该位置可以跳跃的最大长度。
//你的目标是使用最少的跳跃次数到达数组的最后一个位置。

public class problems_045 {

    public static void main(String[] arge){
        new Solution().jump(new int[]{2,3,1,1,4});
    }
    static class Solution {
        public int jump(int[] nums) {
            int end = 0;
            int maxPosition = 0;
            int steps = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                //找能跳的最远的
                maxPosition = Math.max(maxPosition, nums[i] + i);
                if (i == end) { //遇到边界，就更新边界，并且步数加一
                    end = maxPosition;
                    steps++;
                }
            }
            return steps;
        }
    }


//    以下错误


//    static class Solution {
//        public int jump(int[] nums) {
//            // 初始化处理
//            if (null == nums || nums.length == 0 || nums.length == 1) return 0;
//
//            int jump = 0;
//            for (int i = 0; i < nums.length; ) {
//                // 每次尽量跳最大
//                int maxIndex = 0;
//                for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
//                    if(maxIndex < (j + nums[j])) {
//                        maxIndex = (j + nums[j]);
//                    }
//                }
//                jump++;
//                System.out.println("当前index："+i+"，下一个index："+maxIndex+"，jump：" + jump);
//                i = maxIndex;
//                if(maxIndex >= nums.length-1) break;
//            }
//            System.out.println(jump);
//            return jump;
//        }
//    }


//    static class Solution {
//        public int jump(int[] nums) {
//            // 初始化处理
//            if (null == nums || nums.length == 0 || nums.length == 1) return 0;
//            if (nums.length == 2) return 1;
//            // 需要跳跃长度
//            int len = nums.length - nums[0] - 1;
//            // 取下次
//            getNext(nums,0,0);
//            System.out.println(minJump);
//            return minJump;
//        }
//        public Integer minJump = null;
//        public void getNext(int[] nums,int index,Integer jumpNum){
//            System.out.println("getNext,index:" + index + ",jumpNum:" + jumpNum);
//            if(index == nums.length - 1){
//                minJump = null==minJump?jumpNum:Math.min(minJump,jumpNum);
//                System.out.println("---minJump:" + minJump);
//            }
//            if(null != minJump && jumpNum >= minJump){
//                return ;
//            }
//            // 最大跳跃长度
//            int maxJump = nums[index];
//            for (int i = Math.min(index + maxJump, nums.length - 1); i >= index + 1; i--) {
//                getNext(nums,i,jumpNum+1);
//            }
//        }
//    }
}
